#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );

int main() {
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    Print( L1 );
    Print( L2 );
    L = Merge( L1, L2 );
    Print( L );
    Print( L1 );
    Print( L2 );
    return 0;
}

/* 你的代码将被嵌在这里 */

List Read() {
    List L, Head, tmp;
    int len;

    L = ( List )malloc( sizeof( struct Node ) );
    L->Data = 0;
    L->Next = NULL;
    Head = L;
    scanf( "%d", &len );
    for( ;  len--; ) {
        tmp = ( List )malloc( sizeof( struct Node ) );
        scanf( "%d", &( tmp->Data ) );
        tmp->Next = NULL;
        L->Next = tmp;
        L = L->Next;
    }
    return Head;
}

void Print( List L ) {
    if( L->Next ) {
        while( ( L = L->Next ) ) {
            printf( "%d ", L->Data );
        }
    } else
        printf( "NULL" );
    putchar('\n');
}

List Merge( List L1, List L2 ) {
    List Head, tempL;
    List H1, H2;
    H1 = L1;
    H2 = L2;
    L1 = L1->Next;
    L2 = L2->Next;
    Head = malloc( sizeof( struct Node ) );
    Head ->Next=NULL;
    tempL = Head;
    //L1 and L2 is not empty
    while( L1 && L2 ) {
        if( L1->Data > L2->Data ) {
            tempL->Next = L2;
            L2 = L2->Next;
        } else {
            tempL->Next = L1;
            L1 = L1->Next;
        }
        tempL = tempL->Next;
    }
    //when one of them is empty
    if( L1 ) {
        tempL->Next = L1;
    } else if ( L2 ) {
        tempL->Next = L2;
    }
    H1->Next = H2->Next = NULL;
    return Head;
}
